{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Array Given Subset Sums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: recoverArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从子集的和还原数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个未知数组需要你进行还原，给你一个整数 <code>n</code> 表示该数组的长度。另给你一个数组 <code>sums</code> ，由未知数组中全部 <code>2<sup>n</sup></code> 个 <strong>子集的和</strong> 组成（子集中的元素没有特定的顺序）。</p>\n",
    "\n",
    "<p>返回一个长度为 <code>n</code> 的数组<em> </em><code>ans</code><em> </em>表示还原得到的未知数组。如果存在 <strong>多种</strong> 答案，只需返回其中 <strong>任意一个</strong> 。</p>\n",
    "\n",
    "<p>如果可以由数组 <code>arr</code> 删除部分元素（也可能不删除或全删除）得到数组 <code>sub</code> ，那么数组 <code>sub</code> 就是数组 <code>arr</code> 的一个<strong> 子集</strong> 。<code>sub</code> 的元素之和就是 <code>arr</code> 的一个 <strong>子集的和</strong> 。一个空数组的元素之和为 <code>0</code> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>生成的测试用例将保证至少存在一个正确答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, sums = [-3,-2,-1,0,0,1,2,3]\n",
    "<strong>输出：</strong>[1,2,-3]\n",
    "<strong>解释：</strong>[1,2,-3] 能够满足给出的子集的和：\n",
    "- []：和是 0\n",
    "- [1]：和是 1\n",
    "- [2]：和是 2\n",
    "- [1,2]：和是 3\n",
    "- [-3]：和是 -3\n",
    "- [1,-3]：和是 -2\n",
    "- [2,-3]：和是 -1\n",
    "- [1,2,-3]：和是 0\n",
    "注意，[1,2,-3] 的任何排列和 [-1,-2,3] 的任何排列都会被视作正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, sums = [0,0,0,0]\n",
    "<strong>输出：</strong>[0,0]\n",
    "<strong>解释：</strong>唯一的正确答案是 [0,0] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, sums = [0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]\n",
    "<strong>输出：</strong>[0,-1,4,5]\n",
    "<strong>解释：</strong>[0,-1,4,5] 能够满足给出的子集的和。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>sums.length == 2<sup>n</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= sums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-array-given-subset-sums](https://leetcode.cn/problems/find-array-given-subset-sums/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-array-given-subset-sums](https://leetcode.cn/problems/find-array-given-subset-sums/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[-3,-2,-1,0,0,1,2,3]', '2\\n[0,0,0,0]', '4\\n[0,0,5,5,4,-1,4,9,9,-1,4,3,4,8,3,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        mi = -min(sums)\n",
    "        s = SortedList(x + mi for x in sums)\n",
    "        s.pop(0)\n",
    "        ans = [s[0]]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for state in range(1 << i):\n",
    "                if state & 1 << (i - 1):\n",
    "                    t = 0\n",
    "                    for j in range(i):\n",
    "                        if state & 1 << j:\n",
    "                            t += ans[j]\n",
    "                    s.remove(t)\n",
    "            ans.append(s[0])\n",
    "        \n",
    "        for state in range(1 << n):\n",
    "            t = 0\n",
    "            for j in range(n):\n",
    "                if state & 1 << j:\n",
    "                    t += ans[j]\n",
    "            if t == mi:\n",
    "                for j in range(n):\n",
    "                    if state & 1 << j:\n",
    "                        ans[j] *= -1\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        def base(s: List[int]):\n",
    "            if len(s) == 1:\n",
    "                return [0]\n",
    "            diff = s[1] - s[0]\n",
    "            rec, s1, s2 = deque(), [], []\n",
    "            for x in s:\n",
    "                if rec and rec[0] == x - diff:\n",
    "                    s1.append(x - diff)\n",
    "                    s2.append(x)\n",
    "                    rec.popleft()\n",
    "                else:\n",
    "                    rec.append(x)\n",
    "            if 0 in s1 and (r := base(s1)):\n",
    "                return r + [diff]\n",
    "            if 0 in s2 and (r := base(s2)):\n",
    "                return r + [-diff]\n",
    "            return []\n",
    "        return base(sorted(sums))[1:]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        mi = -min(sums)\n",
    "\n",
    "        psums = SortedList([x + mi for x in sums])\n",
    "        psums.pop(0)\n",
    "\n",
    "        ret = []\n",
    "        ret.append(psums[0])\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for mask in range(1 << i):\n",
    "                if (mask >> (i - 1)) & 1:\n",
    "                    s = 0\n",
    "                    for j in range(i):\n",
    "                        if (mask >> j) & 1:\n",
    "                            s += ret[j]\n",
    "\n",
    "                    psums.remove(s)\n",
    "\n",
    "            ret.append(psums[0])\n",
    "\n",
    "        for mask in range(1 << n):\n",
    "            s = 0\n",
    "            for j in range(n):\n",
    "                if (mask >> j) & 1:\n",
    "                    s += ret[j]\n",
    "\n",
    "            if s == mi:\n",
    "                for j in range(n):\n",
    "                    if (mask >> j) & 1:\n",
    "                        ret[j] = -ret[j]\n",
    "\n",
    "                break\n",
    "\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n, sums):\n",
    "        from collections import defaultdict\n",
    "        def allPos(data):\n",
    "            f = [True] * len(data)\n",
    "            c = len(data)\n",
    "            ret = []\n",
    "            while c >= 2:\n",
    "                for i in range(1, len(data)):\n",
    "                    if f[i]:\n",
    "                        step = data[i]\n",
    "                        ret.append(step)\n",
    "                        break\n",
    "                delete = defaultdict(int)\n",
    "                for i in range(len(data)):\n",
    "                    if not f[i]:\n",
    "                        continue\n",
    "                    if data[i] in delete and delete[data[i]] > 0:\n",
    "                        delete[data[i]] -= 1\n",
    "                        f[i] = False\n",
    "                        c -= 1\n",
    "                        continue\n",
    "                    delete[data[i] + step] += 1\n",
    "            return ret\n",
    "        \n",
    "        sums.sort()\n",
    "        bias = -sums[0]\n",
    "        if bias > 0:\n",
    "            sums = [sums[i] + bias for i in range(len(sums))]\n",
    "        ret = allPos(sums)\n",
    "        if bias > 0:\n",
    "            def dfs(i, ls, s):\n",
    "                if s == bias:\n",
    "                    for idx in ls:\n",
    "                        ret[idx] *= -1\n",
    "                    return 1\n",
    "                if i >= len(ret):\n",
    "                    return 0\n",
    "                if dfs(i+1, ls, s): return 1\n",
    "                ls.append(i)\n",
    "                if dfs(i+1, ls, s+ret[i]): return 1\n",
    "                ls.pop(-1)\n",
    "                return 0\n",
    "            dfs(0, [], 0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        sums.sort()\n",
    "        ans = []\n",
    "        test = sums.copy()\n",
    "        while len(test) > 1:\n",
    "            x = test[1] - test[0]\n",
    "            c = Counter(test)\n",
    "            new_test = []\n",
    "            flag = False\n",
    "            for i in sorted(c.keys()):\n",
    "                while c[i]:\n",
    "                    c[i] -= 1\n",
    "                    c[i + x] -= 1\n",
    "                    new_test.append(i)\n",
    "                    if i == 0:\n",
    "                        flag = True\n",
    "            if flag:\n",
    "                ans.append(x)\n",
    "            else:\n",
    "                for i in range(len(new_test)):\n",
    "                    new_test[i] += x\n",
    "                ans.append(-x)\n",
    "            test = new_test\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        m = min(sums)\n",
    "        nums = deque(sorted([num - m for num in sums]))\n",
    "        nums.popleft()\n",
    "        ans = []\n",
    "        pre = []\n",
    "        cnt = Counter(nums)\n",
    "        for _ in range(n):\n",
    "            while not cnt[nums[0]]:\n",
    "                nums.popleft()\n",
    "            x = nums.popleft()\n",
    "            cnt[x] -= 1\n",
    "            for y in pre:\n",
    "                cnt[y + x] -= 1\n",
    "\n",
    "            ans.append(x)\n",
    "            for y in pre[:]:\n",
    "                pre.append(y + x)\n",
    "            pre.append(x)\n",
    "        for j in range(1 << n):\n",
    "            ind = [k for k in range(n) if j & (1 << k)]\n",
    "            if sum(ans[k] for k in ind) == -m:\n",
    "                for k in ind:\n",
    "                    ans[k] *= -1\n",
    "                return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums):\n",
    "        # 提前将数组排好序\n",
    "        sums.sort()\n",
    "\n",
    "        ans = list()\n",
    "        for i in range(n, 1, -1):\n",
    "            d = sums[1] - sums[0]\n",
    "            # 双指针构造 s 和 t\n",
    "            left = right = 0\n",
    "            s, t = list(), list()\n",
    "            # 记录每个子集和是否选过\n",
    "            used = set()\n",
    "            while True:\n",
    "                # left 指针找到最小的未被选择过的子集和\n",
    "                while left < (1 << i) and left in used:\n",
    "                    left += 1\n",
    "                if left == (1 << i):\n",
    "                    break\n",
    "                s.append(sums[left])\n",
    "                used.add(left)\n",
    "                # right 指针找到 sums[left] + d\n",
    "                while right in used or sums[right] != sums[left] + d:\n",
    "                    right += 1\n",
    "                t.append(sums[right])\n",
    "                used.add(right)\n",
    "\n",
    "            if 0 in s:\n",
    "                # 包含 d 并求解 (n-1, s)\n",
    "                ans.append(d)\n",
    "                sums = s\n",
    "            else:\n",
    "                # 包含 -d 并求解 (n-1, t)\n",
    "                ans.append(-d)\n",
    "                sums = t\n",
    "\n",
    "        # 迭代到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数\n",
    "        ans.append(sums[0] + sums[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums):\n",
    "        # 提前将数组排好序\n",
    "        sums.sort()\n",
    "\n",
    "        ans = list()\n",
    "        for i in range(n, 1, -1):\n",
    "            d = sums[1] - sums[0]\n",
    "            # 双指针构造 s 和 t\n",
    "            left = right = 0\n",
    "            s, t = list(), list()\n",
    "            # 记录每个子集和是否选过\n",
    "            used = set()\n",
    "            while True:\n",
    "                # left 指针找到最小的未被选择过的子集和\n",
    "                while left < (1 << i) and left in used:\n",
    "                    left += 1\n",
    "                if left == (1 << i):\n",
    "                    break\n",
    "                s.append(sums[left])\n",
    "                used.add(left)\n",
    "                # right 指针找到 sums[left] + d\n",
    "                while right in used or sums[right] != sums[left] + d:\n",
    "                    right += 1\n",
    "                t.append(sums[right])\n",
    "                used.add(right)\n",
    "\n",
    "            if 0 in s:\n",
    "                # 包含 d 并求解 (n-1, s)\n",
    "                ans.append(d)\n",
    "                sums = s\n",
    "            else:\n",
    "                # 包含 -d 并求解 (n-1, t)\n",
    "                ans.append(-d)\n",
    "                sums = t\n",
    "\n",
    "        # 迭代到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数\n",
    "        ans.append(sums[0] + sums[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums: List[int]) -> List[int]:\n",
    "        low = min(sums)\n",
    "        if low < 0:\n",
    "            sums = [num - low for num in sums]\n",
    "\n",
    "        cnt = Counter(sums)\n",
    "        lst = sorted(cnt.keys())\n",
    "        cnt[0] -= 1\n",
    "        ans = []\n",
    "        pre = defaultdict(int)\n",
    "        pre_sum = []\n",
    "        for _ in range(n):\n",
    "            for num in lst:\n",
    "                if cnt[num] > pre[num]:\n",
    "                    ans.append(num)\n",
    "                    for p in pre_sum[:]:\n",
    "                        pre[p+num] += 1\n",
    "                        pre_sum.append(p+num)\n",
    "                    pre[num] += 1\n",
    "                    pre_sum.append(num)\n",
    "                    break\n",
    "        for i in range(1<<n):\n",
    "            cur = [j for j in range(n) if i & (1<<j)]\n",
    "            if sum(ans[j] for j in cur) == -low:\n",
    "                for j in cur:\n",
    "                    ans[j] *= -1\n",
    "                return ans\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums):\n",
    "        # n 个数构成程度为 2^n 的子集和数组 sums\n",
    "        # 返回值为空表示无解，否则表示有解\n",
    "        def dfs(n: int, sums: List[int]) -> List[int]:\n",
    "            # 递归到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数\n",
    "            # 如果满足该要求，返回剩下的最后一个数，否则返回表示无解的空数组\n",
    "            if n == 1:\n",
    "                if sums[0] == 0:\n",
    "                    return [sums[1]]\n",
    "                if sums[1] == 0:\n",
    "                    return [sums[0]]\n",
    "                return []\n",
    "\n",
    "            d = sums[1] - sums[0]\n",
    "            # 双指针构造 s 和 t\n",
    "            left = right = 0\n",
    "            s, t = list(), list()\n",
    "            # 记录每个子集和是否选过\n",
    "            used = set()\n",
    "            while True:\n",
    "                # left 指针找到最小的未被选择过的子集和\n",
    "                while left < (1 << n) and left in used:\n",
    "                    left += 1\n",
    "                if left == (1 << n):\n",
    "                    break\n",
    "                s.append(sums[left])\n",
    "                used.add(left)\n",
    "                # right 指针找到 sums[left] + d\n",
    "                while right in used or sums[right] != sums[left] + d:\n",
    "                    right += 1\n",
    "                t.append(sums[right])\n",
    "                used.add(right)\n",
    "\n",
    "            # 尝试包含 d 并递归求解 (n-1, s)\n",
    "            ans = dfs(n - 1, s)\n",
    "            if ans:\n",
    "                return ans + [d]\n",
    "\n",
    "            # 尝试包含 -d 并递归求解 (n-1, t)\n",
    "            ans = dfs(n - 1, t)\n",
    "            if ans:\n",
    "                return ans + [-d]\n",
    "            \n",
    "            # 无解返回空数组\n",
    "            return []\n",
    "        \n",
    "        # 提前将数组排好序\n",
    "        sums.sort()\n",
    "        return dfs(n, sums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def recoverArray(self, n: int, sums):\n",
    "        # n 个数构成程度为 2^n 的子集和数组 sums\n",
    "        # 返回值为空表示无解，否则表示有解\n",
    "        def dfs(n: int, sums: List[int]) -> List[int]:\n",
    "            # 递归到 n=1 时，数组中必然一个为 0，另一个为剩下的最后一个数\n",
    "            # 如果满足该要求，返回剩下的最后一个数，否则返回表示无解的空数组\n",
    "            if n == 1:\n",
    "                if sums[0] == 0:\n",
    "                    return [sums[1]]\n",
    "                if sums[1] == 0:\n",
    "                    return [sums[0]]\n",
    "                return []\n",
    "\n",
    "            d = sums[1] - sums[0]\n",
    "            # 双指针构造 s 和 t\n",
    "            left = right = 0\n",
    "            s, t = list(), list()\n",
    "            # 记录每个子集和是否选过\n",
    "            used = set()\n",
    "            while True:\n",
    "                # left 指针找到最小的未被选择过的子集和\n",
    "                while left < (1 << n) and left in used:\n",
    "                    left += 1\n",
    "                if left == (1 << n):\n",
    "                    break\n",
    "                s.append(sums[left])\n",
    "                used.add(left)\n",
    "                # right 指针找到 sums[left] + d\n",
    "                while right in used or sums[right] != sums[left] + d:\n",
    "                    right += 1\n",
    "                t.append(sums[right])\n",
    "                used.add(right)\n",
    "\n",
    "            # 尝试包含 d 并递归求解 (n-1, s)\n",
    "            ans = dfs(n - 1, s)\n",
    "            if ans:\n",
    "                return ans + [d]\n",
    "\n",
    "            # 尝试包含 -d 并递归求解 (n-1, t)\n",
    "            ans = dfs(n - 1, t)\n",
    "            if ans:\n",
    "                return ans + [-d]\n",
    "            \n",
    "            # 无解返回空数组\n",
    "            return []\n",
    "        \n",
    "        # 提前将数组排好序\n",
    "        sums.sort()\n",
    "        return dfs(n, sums)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
